// https://www.lintcode.com/problem/best-time-to-buy-and-sell-stock-with-cooldown/description

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty())
            return 0;
        int n = prices.size();
        vector<int> sell(n);
        vector<int> buy(n);
        sell[0] = 0;
        buy[0] = -prices[0];
        for (int i = 1; i < prices.size(); ++i)
        {
            sell[i] = max(sell[i - 1], buy[i - 1] + prices[i]);
            buy[i] = max(buy[i - 1], (i > 1?sell[i - 2]:0) - prices[i]);
        }
        return sell.back();
    }
};